Generally, cryptosystem implementations include a combination of hardware and software. For example, cryptographic smartcards typically include a hardware microprocessor that executes programs stored in internal secure memory (which can be read-only or updateable). The internal secure memory or other memory is typically used to hold cryptographic keys, which are managed by these programs. Such keys are used in connection with various cryptographic operations including, without limitation, symmetric encryption using DES (Data Encryption Standard), triple DES, IDEA (International Data Encryption Algorithm), SEAL (Software-Optimized Encryption Algorithm), and RC4; public key (asymmetric) encryption and decryption using, RSA and ElGamal; digital signatures using, DSA (Digital Signature Algorithm), ElGamal, and RSA; and Diffie-Hellman key agreement protocols. The key-based operations are, in turn, used to securely process messages being handled by the cryptosystems.
In asymmetric (i.e., public-key based) systems, private keys can be used to create digital signatures and decrypt received data. In the RSA protocol, a sender of a message can use a private key to sign the message, and a recipient of the message can use a public key to verify the origin of the message. In the RSA protocol, a private key may include a modulus (N) for performing modular arithmetic and a secret exponent (d). In mathematics, modular arithmetic (sometimes referred to as “clock arithmetic”) is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value (i.e., the modulus).
The private key has a corresponding public key that includes the modulus (N) and a public exponent (y). For example, Alice may have a private key (N, d) and a public key (N, y) and she may wish to send a message to Bob. Alice's private key (N, d) can be used to send the message to Bob. For example, a hash value of the message can be produced, and the hash value of the message can be raised to the power of d (modulo N) and attached as a signature to the message. When Bob receives the signed message, the same hash algorithm can be used in conjunction with Alice's public key to verify whether the message was sent by Alice. Alice's public key (N, y) can be used to process the signed message. The signature can be raised to the power of y (modulo N), and the resulting hash value can be compared with the message's actual hash value. If the two hash values match, it is determined that the author of the message was in possession of Alice's private key, and that the message has not been tampered with since.
In another example, an authorized entity may generate a cryptographic message (e.g., command) and sign the cryptographic message using a private key (e.g., private key (N, d)), and the hardware in the cryptographic system may use a public key (e.g., public key (N, y)), which corresponds to the private key, to verify that the cryptographic message was generated using the matching private key. As part of the verification, the hardware in the cryptographic system may use a modulus (N), the public exponent (y), and the cryptographic message (cm). The cryptographic system may compute cmy (mod N). The base cm is the message (or, more generically, some quantity derived therefrom or representation thereof). In cases where y=3, traditional cryptographic systems may use three registers of the same size to determine cm3 (mod N). For example, conventional solutions may include a 2048-bit register to store the cryptographic message cm, a 2048-bit register to store cm2 (mod N), and a 2048-bit register to store cm3 (mod N). Traditional solutions generally first compute cm2 (mod N) using modular arithmetic and also use cm2 (mod N) to compute cm3 (mod N), which generally results in significant hardware usage and extensive processing resources (e.g. if registers holding intermediate values are comprised of data in flip flops, register files, SRAM, or other internal storage within a chip performing the calculation).